import copy
import json

grammar5 = {
    "terminals": {"a", "b", "c", "d", "e", "#"},  # 表示结束
    "non_terminals": {"S'", "S", "A", "B"},
    "start": "S'",
    "productions": [
        ("S'", ["S", "$"]),  # (0) S' :== S#
        ("S", ["a", "A", "c", "B", "e"]),  # (1) S :== aAcBe
        ("A", ["b"]),  # (2) A :== b
        ("A", ["A", "b"]),  # (3) A :== Ab
        ("B", ["d"]),  # (4) B :== d
    ],
}
print(grammar5)
AnalyzerTable = {
    # 状态0
    '0': {'a': 'S2',
          'c': '',
          'e': '',
          'b': '',
          'd': '',
          '#': '',
          'S': 'g1',
          'A': '',
          'B': '',
          },
    # 状态1
    '1': {'a': '',
          'c': '',
          'e': '',
          'b': '',
          'd': '',
          '#': 'acc',
          'S': '',
          'A': '',
          'B': '',
          },
    # 状态2
    '2':  {'a': '',
           'c': '',
           'e': '',
           'b': 'S4',
           'd': '',
           '#': '',
           'S': '',
           'A': 'g3',
           'B': '',
           },
    # 状态3
    '3':  {'a': '',
           'c': 'S5',
           'e': '',
           'b': 'S6',
           'd': '',
           '#': '',
           'S': '',
           'A': '',
           'B': '',
           },
    # 状态4
    '4':  {'a': 'r2',
           'c': 'r2',
           'e': 'r2',
           'b': 'r2',
           'd': 'r2',
           '#': 'r2',
           'S': '',
           'A': '',
           'B': '',
           },
    # 状态5
    '5':  {'a': '',
           'c': '',
           'e': '',
           'b': '',
           'd': 'S8',
           '#': '',
           'S': '',
           'A': '',
           'B': 'g7',
           },
    # 状态6
    '6':  {'a': 'r3',
           'c': 'r3',
           'e': 'r3',
           'b': 'r3',
           'd': 'r3',
           '#': 'r3',
           'S': '',
           'A': '',
           'B': '',
           },
    # 状态7
    '7':  {'a': '',
           'c': '',
           'e': 'S9',
           'b': '',
           'd': '',
           '#': '',
           'S': '',
           'A': '',
           'B': '',
           },
    # 状态8
    '8':  {'a': 'r4',
           'c': 'r4',
           'e': 'r4',
           'b': 'r4',
           'd': 'r4',
           '#': 'r4',
           'S': '',
           'A': '',
           'B': '',
           },
    # 状态9
    '9':  {'a': 'r1',
           'c': 'r1',
           'e': 'r1',
           'b': 'r1',
           'd': 'r1',
           '#': 'r1',
           'S': '',
           'A': '',
           'B': '',
           },
}
print(AnalyzerTable)

# LR0语法分析器
def LR0Analyzer(Grammar, InputStr):
    """
    使用LR(0)分析器分析给定的文法和输入字符串。
    
    Args:
        Grammar (dict): 文法字典，包含非终结符、终结符、产生式等信息。
        InputStr (str): 输入字符串。
    
    Returns:
        bool: 分析结果，True表示接受，False表示拒绝。
    """
    StackState = ['0']  # 状态栈初始状态为0
    StackInput = []  # #输入栈
    print(f"(状态栈：{StackState[-1]},输入符号栈：'')")
    length = len(InputStr)
    i = 0
    while (i < length):
        Chr = InputStr[i]  # 获取当前输入字符
        print(f"当前输入：{Chr}")
        TopState = StackState[-1]  # 获取栈顶状态
        Action = AnalyzerTable[TopState][Chr]
        if Action == '':  # 如果没有动作，则报错
            print("Error: No such action")
            return False
        elif Action[0] == 'a':  # 接受动作
            if i == length - 1:  # 如果已经到达输入字符串的末尾，则接受
                print("Accepted")
                return True
        elif Action[0] == 'S':  # 状态转移动作
            StackState.append(Action[1])  # 转移状态
            StackInput.append(Chr)  # 将输入字符压入输入栈
            i = i + 1
            # 栈发生变化后，打印当前状态和输入字符
            print(f"(状态栈：{StackState},输入符号栈：{StackInput})")
        elif Action[0] == 'r':  # 规约动作
            Production = Grammar["productions"][int(Action[1])]
            ProdLeft = Production[0]  # 获取产生式左部
            ProdRight = Production[1]  # 获取产生式右部
            for j in range(len(ProdRight)):  # 弹出len(ProdRight)个状态和字符
                StackState.pop()
                StackInput.pop()
                # 栈发生变化后，打印当前状态和输入字符
                print(f"(状态栈：{StackState},输入符号栈：{StackInput})")
            StackInput.append(ProdLeft)  # 将产生式左部压入输入栈
            # 栈发生变化后，打印当前状态和输入字符
            print(f"(状态栈：{StackState},输入符号栈：{StackInput})")

            # 循环处理状态栈顶的动作，直到没有动作为止
            TopState = StackState[-1]  # 状态发生变化，获取当前状态
            TopSymbol = StackInput[-1]
            Action = AnalyzerTable[TopState][TopSymbol]  # 可能会涉及新的归约或状态转移
            while (Action != '') and ((Action[0] == 'r') or (Action[0] == 'g')):
                if Action[0] == 'r':  # 规约动作
                    Production = Grammar["productions"][int(Action[1])]
                    ProdLeft = Production[0]  # 获取产生式左部
                    ProdRight = Production[1]  # 获取产生式右部
                    for j in range(len(ProdRight)):  # 弹出len(ProdRight)个状态和字符
                        StackState.pop()
                        StackInput.pop()
                        # 栈发生变化后，打印当前状态和输入字符
                        print(f"(状态栈：{StackState},输入符号栈：{StackInput})")
                    StackInput.append(ProdLeft)  # 将产生式左部压入输入栈
                elif Action[0] == 'g':  # 状态转移动作
                    StackState.append(Action[1])  # 转移状态
                    # 栈发生变化后，打印当前状态和输入字符
                    print(f"(状态栈：{StackState},输入符号栈：{StackInput})")
                TopState = StackState[-1]  # 状态发生变化，获取当前状态
                TopSymbol = StackInput[-1]
                Action = AnalyzerTable[TopState][TopSymbol]  # 重新获取当前状态下的动作
            #endwhile

    #endfor
    return False

# 生成所使用的的产生式列表
def GenerateProductionList(Grammar, InputStr):
    OutList = []
    StackState = ['0']  # 状态栈初始状态为0
    StackInput = []  # #输入栈
    print(f"(状态栈：{StackState[-1]},输入符号栈：'')")
    length = len(InputStr)
    i = 0
    while (i < length):
        Chr = InputStr[i]  # 获取当前输入字符
        print(f"当前输入：{Chr}")
        TopState = StackState[-1]  # 获取栈顶状态
        Action = AnalyzerTable[TopState][Chr]
        if Action == '':  # 如果没有动作，则报错
            print("Error: No such action")
            return OutList
        elif Action[0] == 'a':  # 接受动作
            if i == length - 1:  # 如果已经到达输入字符串的末尾，则接受
                print("Accepted")
                return OutList
        elif Action[0] == 'S':  # 状态转移动作
            StackState.append(Action[1])  # 转移状态
            StackInput.append(Chr)  # 将输入字符压入输入栈
            i = i + 1
            # 栈发生变化后，打印当前状态和输入字符
            print(f"(状态栈：{StackState},输入符号栈：{StackInput})")
        elif Action[0] == 'r':  # 规约动作
            Production = Grammar["productions"][int(Action[1])]
            OutList.append(Production) # 将产生式加入输出列表
            ProdLeft = Production[0]  # 获取产生式左部
            ProdRight = Production[1]  # 获取产生式右部
            for j in range(len(ProdRight)):  # 弹出len(ProdRight)个状态和字符
                StackState.pop()
                StackInput.pop()
                # 栈发生变化后，打印当前状态和输入字符
                print(f"(状态栈：{StackState},输入符号栈：{StackInput})")
            StackInput.append(ProdLeft)  # 将产生式左部压入输入栈
            # 栈发生变化后，打印当前状态和输入字符
            print(f"(状态栈：{StackState},输入符号栈：{StackInput})")

            # 循环处理状态栈顶的动作，直到没有动作为止
            TopState = StackState[-1]  # 状态发生变化，获取当前状态
            TopSymbol = StackInput[-1]
            Action = AnalyzerTable[TopState][TopSymbol]  # 可能会涉及新的归约或状态转移
            while (Action != '') and ((Action[0] == 'r') or (Action[0] == 'g')):
                if Action[0] == 'r':  # 规约动作
                    Production = Grammar["productions"][int(Action[1])]
                    OutList.append(Production)# 将产生式加入输出列表
                    ProdLeft = Production[0]  # 获取产生式左部
                    ProdRight = Production[1]  # 获取产生式右部
                    for j in range(len(ProdRight)):  # 弹出len(ProdRight)个状态和字符
                        StackState.pop()
                        StackInput.pop()
                        # 栈发生变化后，打印当前状态和输入字符
                        print(f"(状态栈：{StackState},输入符号栈：{StackInput})")
                    StackInput.append(ProdLeft)  # 将产生式左部压入输入栈
                elif Action[0] == 'g':  # 状态转移动作
                    StackState.append(Action[1])  # 转移状态
                    # 栈发生变化后，打印当前状态和输入字符
                    print(f"(状态栈：{StackState},输入符号栈：{StackInput})")
                TopState = StackState[-1]  # 状态发生变化，获取当前状态
                TopSymbol = StackInput[-1]
                Action = AnalyzerTable[TopState][TopSymbol]  # 重新获取当前状态下的动作
            #endwhile

    #endfor
    return OutList


#递归实现从产生式生成语法树
def SyntaxTree(productionList, index=0, grammar=None):
    """
    根据产生式列表生成语法树
    
    Args:
        productionList (list): 产生式列表
        index (int): 当前产生式索引
        grammar (dict): 语法规则
    
    Returns:
        dict: 语法树字典
    
    """
    TreeDict = {'name': '', 'children': []}
    if index < len(productionList):
        left, right = productionList[index]
        TreeDict['name'] = left  # 设置节点的名字
        ProdIndexOffset = index + 1  # 产生式索引偏移量
        for i in range(len(right)):
            if right[i] in grammar['terminals']:  # 如果是终结符,没有子节点
                child = {'name': right[i], 'children': []}
                TreeDict['children'].append(child)
            else:  # 如果是非终结符,有子节点
                NT = right[i]  # 找到该非终结符对应的产生式
                for j in range(ProdIndexOffset, len(productionList)):  # 从后边的列表元素中找到最先匹配的该非终结符的产生式
                    if NT == productionList[j][0]: # 找到该非终结符对应的最近的一个产生式，并使用
                        child = SyntaxTree(productionList, j, grammar)
                        TreeDict['children'].append(child)
                        ProdIndexOffset = ProdIndexOffset + 1 #下一个非终结符，从后边的产生式中查找
                        break
    return TreeDict


print("LR0 Analyzer Testing 1 --------------------------------")
InputString = "abbcde#"
Rst = LR0Analyzer(grammar5, InputString)
print(f"The syntax of {InputString} is {Rst}")

ProductionList = GenerateProductionList(grammar5, InputString)
ProductionList.reverse()  # 反转列表
print(ProductionList)

Tree = SyntaxTree(ProductionList,index=0,grammar=grammar5)
print(json.dumps(Tree, indent=4))